public class MaxContiguousSumDP  {

	static int findMaxContiguousSum(int input[])
	{

		int n = input.length;

		if(n==0) return 0;
		int[] T = new int[n+1];
		int sum = 0;
		T[0] = input[0];
		T[n] = input[0];
		for(int i = 1; i < n; i++)
		{
			if(input[i]+T[i-1] > input[i] )
				T[i] = T[i-1]+input[i];
			else
				T[i] = input[i];

			if(T[n] < T[i] )
				T[n] = T[i];
		}

		for(int i = 0; i < n; i++)
			System.out.print(T[i]+",");
			System.out.println();
		return(T[n]);
	}

	public static void main(String[] args) {
		int[] A = {-2,-11,-4,-13,-5,-2};
		System.out.println(findMaxContiguousSum(A));
	}
	
}